<!DOCTYPE HTML>
<html lang="en" >
    
    <head>
        
        <meta charset="UTF-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <title>单向链表 | 数据结构与算法（Python）</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 2.6.7">
        
        
        <meta name="HandheldFriendly" content="true"/>
        <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
        <meta name="apple-mobile-web-app-capable" content="yes">
        <meta name="apple-mobile-web-app-status-bar-style" content="black">
        <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
        <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">
        
    <link rel="stylesheet" href="../gitbook/style.css">
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-highlight/website.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-search/search.css">
        
    
        
        <link rel="stylesheet" href="../gitbook/plugins/gitbook-plugin-fontsettings/website.css">
        
    
    

        
    
    
    <link rel="next" href="../chapter3/section3.html" />
    
    
    <link rel="prev" href="../chapter3/index.html" />
    

        
    </head>
    <body>
        
        
    <div class="book"
        data-level="3.1"
        data-chapter-title="单向链表"
        data-filepath="chapter3/section1.md"
        data-basepath=".."
        data-revision="Tue May 23 2017 16:07:52 GMT+0800 (CST)"
        data-innerlanguage="">
    

<div class="book-summary">
    <nav role="navigation">
        <ul class="summary">
            
            
            
            

            

            
    
        <li class="chapter " data-level="0" data-path="index.html">
            
                
                    <a href="../index.html">
                
                        <i class="fa fa-check"></i>
                        
                        数据结构与算法（Python）
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1" data-path="chapter1/index.html">
            
                
                    <a href="../chapter1/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.</b>
                        
                        引入概念
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.1" data-path="chapter1/section1.html">
            
                
                    <a href="../chapter1/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.1.</b>
                        
                        第一次尝试
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="chapter1/section2.html">
            
                
                    <a href="../chapter1/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.2.</b>
                        
                        算法的提出
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="chapter1/section3.html">
            
                
                    <a href="../chapter1/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.3.</b>
                        
                        第二次尝试
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="chapter1/section4.html">
            
                
                    <a href="../chapter1/section4.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.4.</b>
                        
                        算法效率衡量
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="chapter1/section5.html">
            
                
                    <a href="../chapter1/section5.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.5.</b>
                        
                        算法分析
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="chapter1/section6.html">
            
                
                    <a href="../chapter1/section6.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.6.</b>
                        
                        常见时间复杂度
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="chapter1/section7.html">
            
                
                    <a href="../chapter1/section7.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.7.</b>
                        
                        Python内置类型性能分析
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="chapter1/section8.html">
            
                
                    <a href="../chapter1/section8.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>1.8.</b>
                        
                        数据结构
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="2" data-path="chapter2/index.html">
            
                
                    <a href="../chapter2/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.</b>
                        
                        顺序表
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="2.1" data-path="chapter2/section1.html">
            
                
                    <a href="../chapter2/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.1.</b>
                        
                        顺序表的形式
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="chapter2/section2.html">
            
                
                    <a href="../chapter2/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.2.</b>
                        
                        顺序表的结构与实现
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="chapter2/section3.html">
            
                
                    <a href="../chapter2/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.3.</b>
                        
                        顺序表的操作
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="chapter2/section4.html">
            
                
                    <a href="../chapter2/section4.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>2.4.</b>
                        
                        Python中的顺序表
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="3" data-path="chapter3/index.html">
            
                
                    <a href="../chapter3/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.</b>
                        
                        链表
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter active" data-level="3.1" data-path="chapter3/section1.html">
            
                
                    <a href="../chapter3/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.1.</b>
                        
                        单向链表
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="chapter3/section3.html">
            
                
                    <a href="../chapter3/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.2.</b>
                        
                        双向链表
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="chapter3/section2.html">
            
                
                    <a href="../chapter3/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>3.3.</b>
                        
                        单向循环链表
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="4" data-path="chapter4/index.html">
            
                
                    <a href="../chapter4/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.</b>
                        
                        栈
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="4.1" data-path="chapter4/section1.html">
            
                
                    <a href="../chapter4/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>4.1.</b>
                        
                        栈结构实现
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="5" data-path="chapter5/index.html">
            
                
                    <a href="../chapter5/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>5.</b>
                        
                        队列
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="5.1" data-path="chapter5/section1.html">
            
                
                    <a href="../chapter5/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>5.1.</b>
                        
                        队列的实现
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="chapter5/section3.html">
            
                
                    <a href="../chapter5/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>5.2.</b>
                        
                        双端队列
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="6" data-path="chapter6/index.html">
            
                
                    <a href="../chapter6/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.</b>
                        
                        排序与搜索
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="6.1" data-path="chapter6/section1.html">
            
                
                    <a href="../chapter6/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.1.</b>
                        
                        冒泡排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="chapter6/section2.html">
            
                
                    <a href="../chapter6/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.2.</b>
                        
                        选择排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="chapter6/section3.html">
            
                
                    <a href="../chapter6/section3.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.3.</b>
                        
                        插入排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="chapter6/section4.html">
            
                
                    <a href="../chapter6/section4.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.4.</b>
                        
                        快速排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="chapter6/section5.html">
            
                
                    <a href="../chapter6/section5.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.5.</b>
                        
                        希尔排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="chapter6/section6.html">
            
                
                    <a href="../chapter6/section6.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.6.</b>
                        
                        归并排序
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="chapter6/section7.html">
            
                
                    <a href="../chapter6/section7.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.7.</b>
                        
                        常见排序算法效率比较
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="chapter6/section8.html">
            
                
                    <a href="../chapter6/section8.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>6.8.</b>
                        
                        搜索
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="7" data-path="chapter7/index.html">
            
                
                    <a href="../chapter7/index.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>7.</b>
                        
                        树与树算法
                    </a>
            
            
            <ul class="articles">
                
    
        <li class="chapter " data-level="7.1" data-path="chapter7/section1.html">
            
                
                    <a href="../chapter7/section1.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>7.1.</b>
                        
                        二叉树
                    </a>
            
            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="chapter7/section2.html">
            
                
                    <a href="../chapter7/section2.html">
                
                        <i class="fa fa-check"></i>
                        
                            <b>7.2.</b>
                        
                        二叉树的遍历
                    </a>
            
            
        </li>
    

            </ul>
            
        </li>
    


            
            <li class="divider"></li>
            <li>
                <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
                    Published with GitBook
                </a>
            </li>
            
        </ul>
    </nav>
</div>

    <div class="book-body">
        <div class="body-inner">
            <div class="book-header" role="navigation">
    <!-- Actions Left -->
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="../" >数据结构与算法（Python）</a>
    </h1>
</div>

            <div class="page-wrapper" tabindex="-1" role="main">
                <div class="page-inner">
                
                
                    <section class="normal" id="section-">
                    
                        <h1 id="&#x5355;&#x5411;&#x94FE;&#x8868;">&#x5355;&#x5411;&#x94FE;&#x8868;</h1>
<p>&#x5355;&#x5411;&#x94FE;&#x8868;&#x4E5F;&#x53EB;&#x5355;&#x94FE;&#x8868;&#xFF0C;&#x662F;&#x94FE;&#x8868;&#x4E2D;&#x6700;&#x7B80;&#x5355;&#x7684;&#x4E00;&#x79CD;&#x5F62;&#x5F0F;&#xFF0C;&#x5B83;&#x7684;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x5305;&#x542B;&#x4E24;&#x4E2A;&#x57DF;&#xFF0C;&#x4E00;&#x4E2A;&#x4FE1;&#x606F;&#x57DF;&#xFF08;&#x5143;&#x7D20;&#x57DF;&#xFF09;&#x548C;&#x4E00;&#x4E2A;&#x94FE;&#x63A5;&#x57DF;&#x3002;&#x8FD9;&#x4E2A;&#x94FE;&#x63A5;&#x6307;&#x5411;&#x94FE;&#x8868;&#x4E2D;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x800C;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x94FE;&#x63A5;&#x57DF;&#x5219;&#x6307;&#x5411;&#x4E00;&#x4E2A;&#x7A7A;&#x503C;&#x3002;   </p>
<p><img src="../images/&#x5355;&#x94FE;&#x8868;&#x7684;&#x8282;&#x70B9;&#x548C;&#x5355;&#x94FE;&#x8868;.png" alt="&#x5355;&#x5411;&#x94FE;&#x8868;&#x56FE;&#x793A;"></p>
<ul>
<li>&#x8868;&#x5143;&#x7D20;&#x57DF;elem&#x7528;&#x6765;&#x5B58;&#x653E;&#x5177;&#x4F53;&#x7684;&#x6570;&#x636E;&#x3002;</li>
<li>&#x94FE;&#x63A5;&#x57DF;next&#x7528;&#x6765;&#x5B58;&#x653E;&#x4E0B;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x4F4D;&#x7F6E;&#xFF08;python&#x4E2D;&#x7684;&#x6807;&#x8BC6;&#xFF09;</li>
<li>&#x53D8;&#x91CF;p&#x6307;&#x5411;&#x94FE;&#x8868;&#x7684;&#x5934;&#x8282;&#x70B9;&#xFF08;&#x9996;&#x8282;&#x70B9;&#xFF09;&#x7684;&#x4F4D;&#x7F6E;&#xFF0C;&#x4ECE;p&#x51FA;&#x53D1;&#x80FD;&#x627E;&#x5230;&#x8868;&#x4E2D;&#x7684;&#x4EFB;&#x610F;&#x8282;&#x70B9;&#x3002;</li>
</ul>
<h3 id="&#x8282;&#x70B9;&#x5B9E;&#x73B0;">&#x8282;&#x70B9;&#x5B9E;&#x73B0;</h3>
<pre><code class="lang-Python"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SingleNode</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-string">&quot;&quot;&quot;&#x5355;&#x94FE;&#x8868;&#x7684;&#x7ED3;&#x70B9;&quot;&quot;&quot;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self,item)</span>:</span>
        <span class="hljs-comment"># item&#x5B58;&#x653E;&#x6570;&#x636E;&#x5143;&#x7D20;</span>
        self.item = item
        <span class="hljs-comment"># next&#x662F;&#x4E0B;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x6807;&#x8BC6;</span>
        self.next = <span class="hljs-keyword">None</span>
</code></pre>
<h3 id="&#x5355;&#x94FE;&#x8868;&#x7684;&#x64CD;&#x4F5C;">&#x5355;&#x94FE;&#x8868;&#x7684;&#x64CD;&#x4F5C;</h3>
<ul>
<li>is_empty() &#x94FE;&#x8868;&#x662F;&#x5426;&#x4E3A;&#x7A7A;  </li>
<li>length() &#x94FE;&#x8868;&#x957F;&#x5EA6;  </li>
<li>travel() &#x904D;&#x5386;&#x6574;&#x4E2A;&#x94FE;&#x8868;</li>
<li>add(item) &#x94FE;&#x8868;&#x5934;&#x90E8;&#x6DFB;&#x52A0;&#x5143;&#x7D20;</li>
<li>append(item)  &#x94FE;&#x8868;&#x5C3E;&#x90E8;&#x6DFB;&#x52A0;&#x5143;&#x7D20;</li>
<li>insert(pos, item) &#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x6DFB;&#x52A0;&#x5143;&#x7D20;</li>
<li>remove(item) &#x5220;&#x9664;&#x8282;&#x70B9;   </li>
<li>search(item) &#x67E5;&#x627E;&#x8282;&#x70B9;&#x662F;&#x5426;&#x5B58;&#x5728;  </li>
</ul>
<h3 id="&#x5355;&#x94FE;&#x8868;&#x7684;&#x5B9E;&#x73B0;">&#x5355;&#x94FE;&#x8868;&#x7684;&#x5B9E;&#x73B0;</h3>
<pre><code class="lang-Python"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SingleLinkList</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-string">&quot;&quot;&quot;&#x5355;&#x94FE;&#x8868;&quot;&quot;&quot;</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.__head = <span class="hljs-keyword">None</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">is_empty</span><span class="hljs-params">(self)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x5224;&#x65AD;&#x94FE;&#x8868;&#x662F;&#x5426;&#x4E3A;&#x7A7A;&quot;&quot;&quot;</span>
        <span class="hljs-keyword">return</span> self.__head == <span class="hljs-keyword">None</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">length</span><span class="hljs-params">(self)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x94FE;&#x8868;&#x957F;&#x5EA6;&quot;&quot;&quot;</span>
        <span class="hljs-comment"># cur&#x521D;&#x59CB;&#x65F6;&#x6307;&#x5411;&#x5934;&#x8282;&#x70B9;</span>
        cur = self.__head
        count = <span class="hljs-number">0</span>
        <span class="hljs-comment"># &#x5C3E;&#x8282;&#x70B9;&#x6307;&#x5411;None&#xFF0C;&#x5F53;&#x672A;&#x5230;&#x8FBE;&#x5C3E;&#x90E8;&#x65F6;</span>
        <span class="hljs-keyword">while</span> cur != <span class="hljs-keyword">None</span>:
            count += <span class="hljs-number">1</span>
            <span class="hljs-comment"># &#x5C06;cur&#x540E;&#x79FB;&#x4E00;&#x4E2A;&#x8282;&#x70B9;</span>
            cur = cur.next
        <span class="hljs-keyword">return</span> count

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">travel</span><span class="hljs-params">(self)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x904D;&#x5386;&#x94FE;&#x8868;&quot;&quot;&quot;</span>
        cur = self.__head
        <span class="hljs-keyword">while</span> cur != <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">print</span> cur.item,
            cur = cur.next
        <span class="hljs-keyword">print</span> <span class="hljs-string">&quot;&quot;</span>
</code></pre>
<p><strong> &#x5934;&#x90E8;&#x6DFB;&#x52A0;&#x5143;&#x7D20; </strong></p>
<p><img src="../images/&#x5355;&#x94FE;&#x8868;&#x8868;&#x5934;&#x63D2;&#x5165;&#x5143;&#x7D20;.png" alt="&#x5355;&#x94FE;&#x8868;&#x8868;&#x5934;&#x63D2;&#x5165;&#x5143;&#x7D20;"></p>
<pre><code class="lang-Python">    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">add</span><span class="hljs-params">(self, item)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x5934;&#x90E8;&#x6DFB;&#x52A0;&#x5143;&#x7D20;&quot;&quot;&quot;</span>
        <span class="hljs-comment"># &#x5148;&#x521B;&#x5EFA;&#x4E00;&#x4E2A;&#x4FDD;&#x5B58;item&#x503C;&#x7684;&#x8282;&#x70B9;</span>
        node = SingleNode(item)
        <span class="hljs-comment"># &#x5C06;&#x65B0;&#x8282;&#x70B9;&#x7684;&#x94FE;&#x63A5;&#x57DF;next&#x6307;&#x5411;&#x5934;&#x8282;&#x70B9;&#xFF0C;&#x5373;_head&#x6307;&#x5411;&#x7684;&#x4F4D;&#x7F6E;</span>
        node.next = self.__head
        <span class="hljs-comment"># &#x5C06;&#x94FE;&#x8868;&#x7684;&#x5934;_head&#x6307;&#x5411;&#x65B0;&#x8282;&#x70B9;</span>
        self.__head = node
</code></pre>
<p><strong> &#x5C3E;&#x90E8;&#x6DFB;&#x52A0;&#x5143;&#x7D20; </strong></p>
<pre><code class="lang-Python">    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">append</span><span class="hljs-params">(self, item)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x5C3E;&#x90E8;&#x6DFB;&#x52A0;&#x5143;&#x7D20;&quot;&quot;&quot;</span>
        node = SingleNode(item)
        <span class="hljs-comment"># &#x5148;&#x5224;&#x65AD;&#x94FE;&#x8868;&#x662F;&#x5426;&#x4E3A;&#x7A7A;&#xFF0C;&#x82E5;&#x662F;&#x7A7A;&#x94FE;&#x8868;&#xFF0C;&#x5219;&#x5C06;_head&#x6307;&#x5411;&#x65B0;&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">if</span> self.is_empty():
            self.__head = node
        <span class="hljs-comment"># &#x82E5;&#x4E0D;&#x4E3A;&#x7A7A;&#xFF0C;&#x5219;&#x627E;&#x5230;&#x5C3E;&#x90E8;&#xFF0C;&#x5C06;&#x5C3E;&#x8282;&#x70B9;&#x7684;next&#x6307;&#x5411;&#x65B0;&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">else</span>:
            cur = self.__head
            <span class="hljs-keyword">while</span> cur.next != <span class="hljs-keyword">None</span>:
                cur = cur.next
            cur.next = node
</code></pre>
<p><strong> &#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x6DFB;&#x52A0;&#x5143;&#x7D20; </strong></p>
<p><img src="../images/&#x5355;&#x94FE;&#x8868;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x6DFB;&#x52A0;&#x5143;&#x7D20;.png" alt="&#x5355;&#x94FE;&#x8868;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x6DFB;&#x52A0;&#x5143;&#x7D20;"></p>
<pre><code class="lang-Python">    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, pos, item)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x6DFB;&#x52A0;&#x5143;&#x7D20;&quot;&quot;&quot;</span>
        <span class="hljs-comment"># &#x82E5;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;pos&#x4E3A;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x4E4B;&#x524D;&#xFF0C;&#x5219;&#x6267;&#x884C;&#x5934;&#x90E8;&#x63D2;&#x5165;</span>
        <span class="hljs-keyword">if</span> pos &lt;= <span class="hljs-number">0</span>:
            self.add(item)
        <span class="hljs-comment"># &#x82E5;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#x8D85;&#x8FC7;&#x94FE;&#x8868;&#x5C3E;&#x90E8;&#xFF0C;&#x5219;&#x6267;&#x884C;&#x5C3E;&#x90E8;&#x63D2;&#x5165;</span>
        <span class="hljs-keyword">elif</span> pos &gt; (self.length()-<span class="hljs-number">1</span>):
            self.append(item)
        <span class="hljs-comment"># &#x627E;&#x5230;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;</span>
        <span class="hljs-keyword">else</span>:
            node = SingleNode(item)
            count = <span class="hljs-number">0</span>
            <span class="hljs-comment"># pre&#x7528;&#x6765;&#x6307;&#x5411;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;pos&#x7684;&#x524D;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;pos-1&#xFF0C;&#x521D;&#x59CB;&#x4ECE;&#x5934;&#x8282;&#x70B9;&#x5F00;&#x59CB;&#x79FB;&#x52A8;&#x5230;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;</span>
            pre = self.__head
            <span class="hljs-keyword">while</span> count &lt; (pos-<span class="hljs-number">1</span>):
                count += <span class="hljs-number">1</span>
                pre = pre.next
            <span class="hljs-comment"># &#x5148;&#x5C06;&#x65B0;&#x8282;&#x70B9;node&#x7684;next&#x6307;&#x5411;&#x63D2;&#x5165;&#x4F4D;&#x7F6E;&#x7684;&#x8282;&#x70B9;</span>
            node.next = pre.next
            <span class="hljs-comment"># &#x5C06;&#x63D2;&#x5165;&#x4F4D;&#x7F6E;&#x7684;&#x524D;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;next&#x6307;&#x5411;&#x65B0;&#x8282;&#x70B9;</span>
            pre.next = node
</code></pre>
<p><strong> &#x5220;&#x9664;&#x8282;&#x70B9; </strong></p>
<p><img src="../images/&#x5355;&#x94FE;&#x8868;&#x5220;&#x9664;&#x8282;&#x70B9;.png" alt="&#x5355;&#x94FE;&#x8868;&#x5220;&#x9664;&#x8282;&#x70B9;"></p>
<pre><code class="lang-python">    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">remove</span><span class="hljs-params">(self,item)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x5220;&#x9664;&#x8282;&#x70B9;&quot;&quot;&quot;</span>
        cur = self.__head
        pre = <span class="hljs-keyword">None</span>
        <span class="hljs-keyword">while</span> cur != <span class="hljs-keyword">None</span>:
            <span class="hljs-comment"># &#x627E;&#x5230;&#x4E86;&#x6307;&#x5B9A;&#x5143;&#x7D20;</span>
            <span class="hljs-keyword">if</span> cur.item == item:
                <span class="hljs-comment"># &#x5982;&#x679C;&#x7B2C;&#x4E00;&#x4E2A;&#x5C31;&#x662F;&#x5220;&#x9664;&#x7684;&#x8282;&#x70B9;</span>
                <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> pre:
                    <span class="hljs-comment"># &#x5C06;&#x5934;&#x6307;&#x9488;&#x6307;&#x5411;&#x5934;&#x8282;&#x70B9;&#x7684;&#x540E;&#x4E00;&#x4E2A;&#x8282;&#x70B9;</span>
                    self.__head = cur.next
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-comment"># &#x5C06;&#x5220;&#x9664;&#x4F4D;&#x7F6E;&#x524D;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x7684;next&#x6307;&#x5411;&#x5220;&#x9664;&#x4F4D;&#x7F6E;&#x7684;&#x540E;&#x4E00;&#x4E2A;&#x8282;&#x70B9;</span>
                    pre.next = cur.next
                <span class="hljs-keyword">break</span>
            <span class="hljs-keyword">else</span>:
                <span class="hljs-comment"># &#x7EE7;&#x7EED;&#x6309;&#x94FE;&#x8868;&#x540E;&#x79FB;&#x8282;&#x70B9;</span>
                pre = cur
                cur = cur.next
</code></pre>
<p><strong> &#x67E5;&#x627E;&#x8282;&#x70B9;&#x662F;&#x5426;&#x5B58;&#x5728; </strong></p>
<pre><code class="lang-python">    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self,item)</span>:</span>
        <span class="hljs-string">&quot;&quot;&quot;&#x94FE;&#x8868;&#x67E5;&#x627E;&#x8282;&#x70B9;&#x662F;&#x5426;&#x5B58;&#x5728;&#xFF0C;&#x5E76;&#x8FD4;&#x56DE;True&#x6216;&#x8005;False&quot;&quot;&quot;</span>
        cur = self.__head
        <span class="hljs-keyword">while</span> cur != <span class="hljs-keyword">None</span>:
            <span class="hljs-keyword">if</span> cur.item == item:
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span>
            cur = cur.next
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span>
</code></pre>
<p><strong> &#x6D4B;&#x8BD5; </strong></p>
<pre><code class="lang-python"><span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">&quot;__main__&quot;</span>:
    ll = SingleLinkList()
    ll.add(<span class="hljs-number">1</span>)
    ll.add(<span class="hljs-number">2</span>)
    ll.append(<span class="hljs-number">3</span>)
    ll.insert(<span class="hljs-number">2</span>, <span class="hljs-number">4</span>)
    <span class="hljs-keyword">print</span> <span class="hljs-string">&quot;length:&quot;</span>,ll.length()
    ll.travel()
    <span class="hljs-keyword">print</span> ll.search(<span class="hljs-number">3</span>)
    <span class="hljs-keyword">print</span> ll.search(<span class="hljs-number">5</span>)
    ll.remove(<span class="hljs-number">1</span>)
    <span class="hljs-keyword">print</span> <span class="hljs-string">&quot;length:&quot;</span>,ll.length()
    ll.travel()
</code></pre>
<h3 id="&#x94FE;&#x8868;&#x4E0E;&#x987A;&#x5E8F;&#x8868;&#x7684;&#x5BF9;&#x6BD4;">&#x94FE;&#x8868;&#x4E0E;&#x987A;&#x5E8F;&#x8868;&#x7684;&#x5BF9;&#x6BD4;</h3>
<p>&#x94FE;&#x8868;&#x5931;&#x53BB;&#x4E86;&#x987A;&#x5E8F;&#x8868;&#x968F;&#x673A;&#x8BFB;&#x53D6;&#x7684;&#x4F18;&#x70B9;&#xFF0C;&#x540C;&#x65F6;&#x94FE;&#x8868;&#x7531;&#x4E8E;&#x589E;&#x52A0;&#x4E86;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;&#x57DF;&#xFF0C;&#x7A7A;&#x95F4;&#x5F00;&#x9500;&#x6BD4;&#x8F83;&#x5927;&#xFF0C;&#x4F46;&#x5BF9;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#x7684;&#x4F7F;&#x7528;&#x8981;&#x76F8;&#x5BF9;&#x7075;&#x6D3B;&#x3002;</p>
<p>&#x94FE;&#x8868;&#x4E0E;&#x987A;&#x5E8F;&#x8868;&#x7684;&#x5404;&#x79CD;&#x64CD;&#x4F5C;&#x590D;&#x6742;&#x5EA6;&#x5982;&#x4E0B;&#x6240;&#x793A;&#xFF1A;  </p>
<table>
<thead>
<tr>
<th>&#x64CD;&#x4F5C;</th>
<th style="text-align:center">&#x94FE;&#x8868;</th>
<th>&#x987A;&#x5E8F;&#x8868;</th>
</tr>
</thead>
<tbody>
<tr>
<td>&#x8BBF;&#x95EE;&#x5143;&#x7D20;</td>
<td style="text-align:center">O(n)</td>
<td>O(1)</td>
</tr>
<tr>
<td>&#x5728;&#x5934;&#x90E8;&#x63D2;&#x5165;/&#x5220;&#x9664;</td>
<td style="text-align:center">O(1)</td>
<td>O(n)</td>
</tr>
<tr>
<td>&#x5728;&#x5C3E;&#x90E8;&#x63D2;&#x5165;/&#x5220;&#x9664;</td>
<td style="text-align:center">O(n)</td>
<td>O(1)</td>
</tr>
<tr>
<td>&#x5728;&#x4E2D;&#x95F4;&#x63D2;&#x5165;/&#x5220;&#x9664;</td>
<td style="text-align:center">O(n)</td>
<td>O(n)</td>
</tr>
</tbody>
</table>
<p>&#x6CE8;&#x610F;&#x867D;&#x7136;&#x8868;&#x9762;&#x770B;&#x8D77;&#x6765;&#x590D;&#x6742;&#x5EA6;&#x90FD;&#x662F; O(n)&#xFF0C;&#x4F46;&#x662F;&#x94FE;&#x8868;&#x548C;&#x987A;&#x5E8F;&#x8868;&#x5728;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x65F6;&#x8FDB;&#x884C;&#x7684;&#x662F;&#x5B8C;&#x5168;&#x4E0D;&#x540C;&#x7684;&#x64CD;&#x4F5C;&#x3002;&#x94FE;&#x8868;&#x7684;&#x4E3B;&#x8981;&#x8017;&#x65F6;&#x64CD;&#x4F5C;&#x662F;&#x904D;&#x5386;&#x67E5;&#x627E;&#xFF0C;&#x5220;&#x9664;&#x548C;&#x63D2;&#x5165;&#x64CD;&#x4F5C;&#x672C;&#x8EAB;&#x7684;&#x590D;&#x6742;&#x5EA6;&#x662F;O(1)&#x3002;&#x987A;&#x5E8F;&#x8868;&#x67E5;&#x627E;&#x5F88;&#x5FEB;&#xFF0C;&#x4E3B;&#x8981;&#x8017;&#x65F6;&#x7684;&#x64CD;&#x4F5C;&#x662F;&#x62F7;&#x8D1D;&#x8986;&#x76D6;&#x3002;&#x56E0;&#x4E3A;&#x9664;&#x4E86;&#x76EE;&#x6807;&#x5143;&#x7D20;&#x5728;&#x5C3E;&#x90E8;&#x7684;&#x7279;&#x6B8A;&#x60C5;&#x51B5;&#xFF0C;&#x987A;&#x5E8F;&#x8868;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x65F6;&#x9700;&#x8981;&#x5BF9;&#x64CD;&#x4F5C;&#x70B9;&#x4E4B;&#x540E;&#x7684;&#x6240;&#x6709;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x524D;&#x540E;&#x79FB;&#x4F4D;&#x64CD;&#x4F5C;&#xFF0C;&#x53EA;&#x80FD;&#x901A;&#x8FC7;&#x62F7;&#x8D1D;&#x548C;&#x8986;&#x76D6;&#x7684;&#x65B9;&#x6CD5;&#x8FDB;&#x884C;&#x3002;</p>

                    
                    </section>
                
                
                </div>
            </div>
        </div>

        
        <a href="../chapter3/index.html" class="navigation navigation-prev " aria-label="Previous page: 链表"><i class="fa fa-angle-left"></i></a>
        
        
        <a href="../chapter3/section3.html" class="navigation navigation-next " aria-label="Next page: 双向链表"><i class="fa fa-angle-right"></i></a>
        
    </div>
</div>

        
<script src="../gitbook/app.js"></script>

    
    <script src="../gitbook/plugins/gitbook-plugin-search/lunr.min.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-search/search.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-sharing/buttons.js"></script>
    

    
    <script src="../gitbook/plugins/gitbook-plugin-fontsettings/buttons.js"></script>
    

<script>
require(["gitbook"], function(gitbook) {
    var config = {"highlight":{},"search":{"maxIndexSize":1000000},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2}};
    gitbook.start(config);
});
</script>

        
    </body>
    
</html>
